package simple.t6073.largestInteger;


import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/largest-number-after-digit-swaps-by-parity
 * 给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。
 * 返回交换 任意 次之后 num 的 最大 可能值。
 *
 * 想法：
 * 先记录每一位的奇偶性，然后将奇数和偶数分组排序，排序完成后再组合到一起
 *
 * 执行用时：1 ms, 在所有 Java 提交中击败了100%的用户
 * 内存消耗：38 MB, 在所有 Java 提交中击败了100%的用户
 * 此题为周赛题目，击败100%是无意义的数据
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.largestInteger(1234));
    }

    /**
     * 计算交换数字可获得的最大正整数
     */
    public int largestInteger(int num) {
        List<Integer> parity = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        List<Integer> odd = new ArrayList<>();
        chuli(parity, even, odd, num);
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        };
        Collections.sort(even, comparator);
        Collections.sort(odd, comparator);
        int res = 0;
        int m = 0;
        int n = 0;
        for (int i = parity.size() - 1; i >= 0; i--) {
            if (parity.get(i) == 0) {
                res = res * 10 + even.get(m++);
            } else {
                res = res * 10 + odd.get(n++);
            }
        }
        return res;
    }

    /**
     * 先记录每一位的奇偶性，然后将奇数和偶数分组排序
     */
    public void chuli(List<Integer> parity, List<Integer> even, List<Integer> odd, int num) {
        if (num == 0) {
            return;
        }
        int currentDigit = num % 10;
        num /= 10;
        if (currentDigit % 2 == 0) {
            parity.add(0);
            even.add(currentDigit);
        } else {
            parity.add(1);
            odd.add(currentDigit);
        }
        chuli(parity, even, odd, num);
    }
}
